#include <iostream>
#include <string>
using namespace std;

#define MaxSize 50
typedef struct {
    char data[MaxSize];
    int top;
}SqStack;

//用栈实现逆波兰表达式（后缀表达式）

//初始化
void InitStack(SqStack &S){
    S.top = -1;
}

//判空
bool StackEmpty(SqStack S){
    if(S.top == -1){
        return true;
    }
    return false;
}

//进栈
bool Push(SqStack &S, char x){
    if(S.top == MaxSize - 1){
        return false;
    }
    S.top++;
    S.data[S.top] = x;
    return true;
}

//出栈
bool Pop(SqStack &S, char &x){
    if(S.top == -1){
        return false;
    }
    x = S.data[S.top--];
    return true;
}

//读取栈顶元素
char GetTop(SqStack S){
    if(S.top == -1){
        return NULL;
    }
    return S.data[S.top];
}

bool Createlate(string s){
    // SqStack stack;
    // int i;
    // int c;
    // for(int i = 0; i < s.length(); i++){
    //     if(s[i] >= 0 && s[i] <= 9){                      //将数字抽取出来

    //     }
    // }
    return true;
}


void  PrintStack(SqStack S){
    int l = S.top;
    for(int i = 0; i <= l; i++){
        cout << S.data[i] << " ";
    }
    cout << endl;
}

//低级括号匹配 ---------------- 不在乎括号的层级关系 {[()]}
bool PiPei(string s){
    while (s != "")
    {
        int l = s.length();
        SqStack stack;
        InitStack(stack);
        char x = ' ';
        for(int i = 0; i < l; i++){
            if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
                Push(stack,s[i]);
                cout<<"进栈"<<endl;
                PrintStack(stack);
                continue;
            }
            if(s[i] == ')'){
                Pop(stack, x);
                cout<<"出栈"<<endl;
                if(x != '('){
                    return false;
                }
                x = ' ';
                continue;
            }
            if(s[i] == ']'){
                Pop(stack, x);
                cout<<"出栈"<<endl;
                if(x != '['){
                    return false;
                }
                x = ' ';
                continue;
            }
            if(s[i] == '}'){
                Pop(stack, x);
                cout<<"出栈"<<endl;
                if(x != '{'){
                    return false;
                }
                x = ' ';
                continue;
            }
        }
        if (StackEmpty(stack))
        {
            return true;
        } 
        return false;
    }
    return true;
}

//高级括号匹配 ---------------- 在乎括号的层级关系 {[()]}
bool PiPei2(string s){
    while (s != "")
    {
        int l = s.length();
        SqStack stack;
        InitStack(stack);
        char x = ' ';
        for(int i = 0; i < l; i++){
            if(s[i] == '('){
                Push(stack,s[i]);
                cout<<"进栈"<<endl;
                PrintStack(stack);
                continue;
            }
            if(s[i] == '['){   
                if(GetTop(stack) == '('){
                    return false;
                }
                Push(stack,s[i]);
                cout<<"进栈"<<endl;
                PrintStack(stack);
                continue;
            }
            if(s[i] == '{'){
                char x = GetTop(stack);
                if(x == '(' || x == '['){
                    return false;
                }
                Push(stack,s[i]);
                cout<<"进栈"<<endl;
                PrintStack(stack);
                x = ' ';
                continue;
            }
            if(s[i] == ')'){
                Pop(stack, x);
                cout<<"出栈"<<endl;
                if(x != '('){
                    return false;
                }
                x = ' ';
                continue;
            }
            if(s[i] == ']'){
                Pop(stack, x);
                cout<<"出栈"<<endl;
                if(x != '['){
                    return false;
                }
                x = ' ';
                continue;
            }
            if(s[i] == '}'){
                Pop(stack, x);
                cout<<"出栈"<<endl;
                if(x != '{'){
                    return false;
                }
                x = ' ';
                continue;
            }
        }
        if (StackEmpty(stack))
        {
            return true;
        } 
        return false;
    }
    return true;
}


int main()
{
    cout << "输入一串数学式子生成逆波兰表达式" << endl;
    string s = "20 + 40 * (23 + 7) / 4 - 4";
    string s1 = "{{{{{{{}{}{}{}{}}{}{}}}}}}}}[][][][][][][][][}{}{}{}{}";
    string s2 = "[{}]{}()45666{}{{{[]}}}(())";
    if(PiPei(s2)){
        cout << "匹配成功" << endl;
        return 0;
    }
    cout << "匹配失败" << endl;
    return 0;
    
}
